class Solution {
public:
    string minWindow(string s, string t) {
        if (s.empty() || t.empty())
            return "";
        unordered_map<char, int> t_num;
        for (char c : t) {
            t_num[c]++;
        }

        int kinds = t_num.size();
        unordered_map<char, int> window_num;
        int left = 0, right = 0;
        int targets= 0;
        int min_len = INT_MAX;
        int min_left = 0;

        while (right < s.size()) {
            char c = s[right];
            window_num[c]++;
            if (t_num.find(c) != t_num.end() && window_num[c] == t_num[c]) {
                targets++;
            }

            while (left <= right && targets == kinds) {
                if (right - left + 1 < min_len) {
                    min_len = right - left + 1;
                    min_left = left;
                }

                char left_char = s[left];
                window_num[left_char]--;
                if (t_num.find(left_char) != t_num.end() && window_num[left_char] < t_num[left_char]) {
                    targets--;
                }
                left++;
            }

            right++;
        }

        if (min_len == INT_MAX) return "";
        return s.substr(min_left, min_len);
    }
};

